package top.lcm668.study.oj.base.sortmethods;

/**
 * @author: Coder-Lcm
 * @date: 2021/10/5 6:33
 * 插入排序
 */
public class InsertSort<T extends Comparable<T>> extends BaseSort<T> {

    @Override
    protected void sort(T[] arr, boolean isAsc) {
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            int curTimes = 0;
            for (int i1 = i; i1 > 0; i1--) {
                curTimes++;
                if (isAsc ? lessThan(arr[i1], arr[i1 - 1]) : largeThan(arr[i1], arr[i1 - 1])) {
                    swap(arr, i1, i1 - 1);
                } else {
                    // 如果当前数跟已排序的序列末端元素 也有序，则无需再往前比较了，继续下一趟
                    break;
                }
            }
            System.out.println(curTimes);
        }
    }
}
